/*
 * @Author: szx
 * @Date: 2022-03-13 17:16:00
 * @LastEditTime: 2022-03-13 20:30:58
 * @Description:
 * @FilePath: \leetcode\other\银联-03. 理财产品\银联-03. 理财产品.js
 */
/**
 * @param {number[]} product
 * @param {number} limit
 * @return {number}
 */
var maxInvestment = function (product, limit) {
    product.sort((a, b) => b - a);
    const mod = 1e9 + 7;
    product.push(0);
    const n = product.length;
    let start = 0;
    let len = 0;
    let res = 0;
    for (let i = 0; i < n - 1; i++) {
        if (product[i] == product[i + 1]) continue;
        len = i - start + 1 + len;
        for (let j = product[i]; j > product[i + 1]; j--) {
            const num = Math.min(len, limit);
            res = (res + j * num) % mod;
            limit -= num;
            if (limit == 0) return res;
        }
        start = i + 1;
    }
    return res;
};
console.log(maxInvestment([4, 5, 3], 8));
console.log(maxInvestment([2, 1, 3], 20));
console.log(maxInvestment([2, 1, 5, 8, 7], 10));
console.log(maxInvestment([43877, 10848, 10442, 48132, 83395, 71523, 60275, 39527], 345056));
